package org.gzc.linklist;

/**
 * @Description: 合并两个有序的链表，合并后的链表仍然有序
 * @Author: guozongchao
 * @Date: 2020/8/3 11:03
 */
public class MergeTwoLinkList {
    public static void main(String[] args) {
        //测试数据
        StudentNode node1 = new StudentNode(1, "张三");
        StudentNode node2 = new StudentNode(5, "李四");
        StudentNode node3 = new StudentNode(3, "王五");
        StudentNode node4 = new StudentNode(12, "赵六");
        StudentNode node5 = new StudentNode(9, "马云");
        StudentNode node6 = new StudentNode(11, "lalalalalal");


        SingleLinkList linkList1 = new SingleLinkList();
        SingleLinkList linkList2 = new SingleLinkList();

        linkList1.addByOrder(node1);
        linkList1.addByOrder(node3);
        linkList1.addByOrder(node5);
        linkList2.addByOrder(node4);
        linkList2.addByOrder(node2);
        linkList2.addByOrder(node6);
        System.out.println("\n合并前链表1:");
        linkList1.display();
        System.out.println("\n合并前链表2:");
        linkList2.display();

        //合并
        StudentNode merge = merge(linkList1.getHead(), linkList2.getHead());

        //合并后打印
        System.out.println("\n合并后链表：");
        SingleLinkList linkList3 = new SingleLinkList(merge.next);
        linkList3.display();



    }

    // 合并两个有序链表

    public static StudentNode merge(StudentNode targetNode, StudentNode sourceNode) {
        if (targetNode.next == null) {
            return sourceNode;
        }
        if (sourceNode.next == null) {
            return targetNode;
        }
        SingleLinkList linkList = new SingleLinkList(targetNode.next);
        StudentNode head = sourceNode;
        while (head.next != null) {
            StudentNode node = head.next;
            head.next = head.next.next;
            linkList.addByOrder(node);  //按序添加  注意位置必须在头结点与后面的结点连接后在进行添加，否则导致链表错乱
        }
        return linkList.getHead();
    }
}